package ch18._07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;

import ch18.Util;

public class Solution {
    public static String findLongest(String[] array) {
//	String[] array = new String[words.size()];
//	array = words.toArray(array);
    	
    /**
     * Good Question. Should not use String.CASE_INSENSITIVE_ORDER here.
     * Use length comparator instead.
     */
//	Arrays.sort(array, String.CASE_INSENSITIVE_ORDER);
    	Arrays.sort(array, new Comparator<String>() {
    		public int compare(String s1, String s2) {
    			if (s1.length() > s2.length()) {
    				return 1;
    			} else if (s1.length() < s2.length()) {
    				return -1;
    			} else 
    				return s1.compareTo(s2);
    		}
		});
	Map<String, Boolean> map = new HashMap<String, Boolean>();
	/**
	 * Good Question!!
	 * At first, I missed the following for statements, and it ends up with hashMap 
	 * stack overflow exception!!
	 */
	//================================
	for (String str : array) {
		map.put(str, true);
	}
	//================================
	for (int i = array.length - 1; i >= 0; i--) {
//	for (int i = 0; i < array.length; i--) {
	    boolean valid = test(array[i], array, true, map);
	    if (valid) {
		return array[i];
	    }
	}
	return "";
    }

    private static boolean test(String s, String[] array, boolean isOriginal, Map<String, Boolean> map) {
	if (s == "") {
	    return true;
	}
	if (map.containsKey(s) && !isOriginal) {
	    return map.get(s);
	}
	for (String str : array) {
	    if (s.startsWith(str)) {
		boolean valid = test(s.substring(str.length()), array, false, map);
		if (valid) {
		    map.put(s, valid);
		    return true;
		}
	    }
	}
	map.put(s, false);
	return false;
    }
    
    public static void main(String[] args) {
		String[] arr = Util.createGiantArray();
		String s = findLongest(arr);
		System.out.println(s);
	}
}